There are many situations in which a data stream is transmitted from a transmitter to a receiver over a communication channel. A communication channel may exist in one (or more) of many different possible networks. For example, a communication channel may exist in the internet or in a wireless network such as a mobile telecommunications network. The data in a data stream may be divided into data packets for transmission over a communication channel. The protocol for dividing the data into data packets (e.g. the form of the headers of the data packets, and other such implementation details) may depend upon the nature of the communication channel on which the data is to be transmitted, e.g. the type of network through which the data packet is to be transmitted. The data may be encoded by an encoder prior to transmission from the transmitter and decoded by a decoder after reception at the receiver.
In an ideal system, the communication channel is lossless such that every data packet transmitted from the transmitter over the communication channel is received at the receiver. However, in real physical systems, the communication channel may be lossy, meaning that some of the transmitted data packets will be lost on the communication channel and as such will not be received at the receiver. This may be detrimental. Correction schemes can be used to help recover, at the receiver, at least some of the lost data packets.
As an example, forward error correction (FEC) is one correction scheme which can be used to combat packet loss in a communication channel FEC produces redundant data (as FEC data units) in addition to the original data packets and includes the FEC data units in the data stream which is transmitted over the communication channel. The redundant FEC data units may be placed in their own packets, separate to the data packets in the data stream. Alternatively, or additionally, the FEC data units may be appended (or “piggybacked”) to the original data packets in the data stream. When some of the original data packets are lost in the communication channel, the successfully arrived FEC data units and the successfully arrived data packets can be used to recover (at least some of) the lost data packets. That is, FEC reduces the packet loss seen by a decoder of the receiver, compared to the actual packet loss in the communication channel.
FIGS. 1a, 1b and 1c illustrate three examples of how a FEC data unit may be generated. As illustrated in FIG. 1a, a FEC data unit 104 may be generated as an exact copy of an original data packet 102 of the data stream. By including both the data packet 102 and the FEC data unit 104 in the data stream, the data in the data packet 102 is transmitted twice. Therefore if the data packet 102 is lost during transmission but the FEC data unit 104 is successfully received then the data in the data packet 102 can be successfully recovered at the receiver (using the FEC data unit 104). As illustrated in FIG. 1b a module 108 may be used to generate a FEC data unit 110 which is a copy of an original data packet 106 encoded at a lower bit rate. If the data packet 106 is lost during transmission but the FEC data unit 110 is successfully received then the data in the data packet 106 can be at least partially recovered at the receiver based on the FEC data unit 110. It should be noted that if the data packets 102 and 106 have the same size (e.g. the same number of bits) then the FEC data unit 110 will have a smaller size (e.g. fewer bits) than the FEC data unit 104. Therefore, although the FEC data unit 104 may be more useful in recovering the data packet 102 than the FEC data unit 110 is in recovering the data packet 106, it may be beneficial to generate FEC data units as shown in FIG. 1b since the FEC data unit 110 uses less of the available bit rate on the communication channel for the data stream than the FEC data unit 104 uses. As illustrated in FIG. 1c a mixing module 118 may be used to generate a FEC data unit 120 from a plurality of the original data packets, e.g. data packets 112, 114 and 116. Finite field (Galois field) arithmetic may be used to combine original data packets. For example the mixing module 118 may determine the bit-by-bit result of an XOR function applied to the three data packets 112, 114 and 116 to generate the FEC data unit 120. In another approach, data packets 112, 114 and 116 are combined byte-by-byte using Galois field GF(28) arithmetic to generate the FEC data unit 120. In this sense the FEC data unit 120 is the result of combining or mixing the original data packets 112, 114 and 116. If one of the data packets 112, 114 and 116 is lost during transmission but the other two data packets and the FEC data unit 120 are successfully received then the data in the lost data packet can be successfully recovered at the receiver (using the other two data packets and the FEC data unit 120).
It can therefore be seen that FEC data units may be generated in a number of different ways. Different FEC schemes describe different ways in which the FEC data units are to be generated. A FEC scheme may describe factors relating to the generation of the FEC data units, such as: the number of FEC data units that are generated; which data packets are used to generate the FEC data units; how the FEC data units are transmitted (e.g. as separate packets or by appending the FEC data units to the data packets); and where in the data stream the FEC data units are placed. The loss-recovery performance of a FEC scheme describes the ability of the FEC scheme to recover lost data packets at the receiver using the FEC data units.
Generally, increasing the number of FEC data units in the data stream improves the loss-recovery performance of a FEC scheme. However, increasing the number of FEC data units in the data stream comes at a cost of bit rate efficiency. If the coding bit rate of original data packets is kept unchanged, then increased redundancy (e.g. by increasing the number of FEC data units in the data stream) leads to increased total bit rate. Alternatively, if the total bit rate available for the data stream on the communication channel is constrained, then increased redundancy (e.g. by increasing the number of FEC data units in the data stream) comes at a price of reduced coding bit rate of the original data packets. It is therefore an aim to balance the conflicting factors of the loss-recovery performance of the FEC with the bit rate efficiency of the data stream.
One class of algorithm for designing an appropriate FEC scheme is based on error-correcting and erasure codes known from communication theory. One example of such codes is Reed-Solomon codes. The codes are designed according to certain scenarios in which the FEC may operate, to ensure recovery of all lost data packets if the number of lost data packets does not exceed a predetermined maximum.
Another class of algorithm for designing an appropriate FEC scheme is based on training. Training is performed offline. Given channel conditions, and coding requirements for the FEC data units (e.g. (i) the FEC overhead which sets the ratio of redundant data relative to the original data in the data stream, for example the number of FEC data units relative to the number of original data packets in the data stream, and (ii) the FEC depth which sets the maximum allowable displacement in the data stream between the oldest and the newest data packet that can be protected by (or combined into) each FEC data unit), optimal combinations/mixings of the original data packets are trained to optimize for a loss-recovery performance within an optimization window. Since the number of relevant channel conditions, FEC overheads, and FEC depths can be high, the number of trained schemes can be high too.
The classes of algorithm for designing an appropriate FEC scheme described above determine an appropriate FEC scheme for use within an optimization window. That is, a FEC scheme is set for the optimization window with the aim of optimizing the performance of the FEC during the optimization window. The optimization window may be a length of time (e.g. ten seconds) or the optimization window may be a number of data packets of the data stream (e.g. a hundred data packets). At the end of the optimization window, the FEC scheme may be set again for the next optimization window.